package hot;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Num15 {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for(int fir = 0; fir < n; fir++) {
            if(fir > 0 && nums[fir] == nums[fir - 1]) {
                continue;
            }
            int target = -nums[fir];
            int thrid = n - 1;
            for(int sec = fir + 1; sec < n; sec++) {
                if(sec > fir + 1 && nums[sec] == nums[sec - 1]) {
                    continue;
                }
                while(thrid > sec && nums[sec] + nums[thrid] > target) {
                    thrid--;
                }
                if(sec == thrid) {
                    break;
                }
                if(nums[sec] + nums[thrid] == target) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[fir]);
                    list.add(nums[sec]);
                    list.add(nums[thrid]);
                    res.add(list);
                }
            }
        }
        return res;
    }
}
